Group items tagged

Описание и примеры использования эффективной эвристики для решения задачи коммивояжера "LKH is an effective implementation of the Lin-Kernighan heuristic for solving the traveling salesman problem." Computational experiments have shown that LKH is highly effective. Even though the algorithm is approximate, optimal solutions are produced with an impressively high frequency. LKH has produced optimal solutions for all solved problems we have been able to obtain; including a 85,900-city instance (at the time of writing, the largest nontrivial instance solved to optimality). Furthermore, the algorithm has improved the best known solutions for a series of large-scale instances with unknown optima, among these a 1,904,711-city instance (World TSP)."

Цель данного исследования - разработка инструмента, способного решать задачи оптимизации круговых рейсов, основываясь на критерии длины маршрута. Для достижения цели разработаны прототип модели на MS Excel и модель в среде моделирования AnyLogic. Адекватность обеих моделей доказана совпадением результатов моделирования с решениями, получаемыми методами полного перебора на примерах малой размерности. Особенность данной задачи заключается в том, что количество возможных маршрутов N=n! ,где n количество пунктов захода судна, может находиться за пределом Бремермана. Следовательно, задача станет трансвычислительной, а решить ее возможно методом генетического алгоритма. В классической форме алгоритма при его цикличном движении возможно фиксирование алгоритма на локальном экстремуме пространства, именно поэтому в него вводятся механизмы мутации с определенной частотой. Но авторы данной работы отметили, что данный способ не подходит для решения задачи коммивояжера, поскольку существует вероятность повторения/утраты отдельных пунктов захода. Поэтому авторами был предложен механ